package com.moyoutian.leetcode;

/**
 * 41. 缺失的第一个正数
 * <p>
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * <p>
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,0]
 * 输出：3
 * 示例 2：
 * <p>
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 * 示例 3：
 * <p>
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 5 * 105
 * -231 <= nums[i] <= 231 - 1
 */
public class Demo41 {
    //思路找的数字范围小所以可以借用数组下标
    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{2, 1}));
    }

    //交换值到下标
    public static int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        } else if (nums.length == 1) {
            return nums[0] == 1 ? 2 : 1;
        }

        int temp = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            //当前值在数组下标内且  位置不对 (nums[temp] - 1 != temp)   ,交换目标值和被交换值不能相等nums[temp] != nums[nums[temp] - 1]
            while (0 <= nums[temp] - 1 && nums[temp] - 1 < nums.length && nums[temp] - 1 != temp && nums[temp] != nums[nums[temp] - 1]) {
                ws(nums, temp, nums[temp] - 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i] - 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    /**
     * 交换
     */
    public static void ws(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}
